import java.util.*;

class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode(int val) {
        this.val = val;
    }
}
public class TestDemo9A {
    TreeNode prev = null;

    //将二叉树转成有序的双向链表
    public void inorder(TreeNode pCur) {
        if (pCur == null) {
            return;
        }
        inorder(pCur.left);
        pCur.left = prev;
        if (prev != null) {
            prev.right = pCur;
        }
        prev = pCur;
        System.out.print(pCur.val + " ");
        inorder(pCur.right);
    }

    public TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree == null) {
            return null;
        }
        inorder(pRootOfTree);
        TreeNode head = pRootOfTree;
        while (head.left != null) {
            head = head.left;
        }
        return head;
    }

    //根据前序和中序遍历二叉树
    public int preIndex = 0;

    public TreeNode createTreeByPandI(int[] preorder, int[] inorder, int inbegin, int inend) {
        if (inbegin > inend) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[preIndex]);
        int rootIndex = findIndexOfI(inorder, inbegin, inend, preorder[preIndex]);
        if (rootIndex == -1) {
            return null;
        }
        preIndex++;
        root.left = createTreeByPandI(preorder, inorder, inbegin, rootIndex - 1);
        root.right = createTreeByPandI(preorder, inorder, rootIndex + 1, inend);
        return root;
    }

    public int findIndexOfI(int[] inorder, int inbegin, int inend, int key) {
        for (int i = inbegin; i <= inend; i++) {
            if (inorder[i] == key) {
                return i;
            }
        }
        return -1;
    }

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || inorder == null) {
            return null;
        }
        return createTreeByPandI(preorder, inorder, 0, inorder.length - 1);
    }


    //二叉树创建字符串
    public void tree2strChild(TreeNode root, StringBuilder sb) {
        if (root == null) {
            return;
        }
        sb.append(root.val);//前序遍历，先将根节点加入可变字符串中
        if (root.left == null) {//左树为空（还得考虑右树的情况）
            //如果右树为空，说明当前根节点没有孩子节点
            if (root.right == null) {
                return;
            } else {//左树为空，右树不为空直接加（）
                sb.append("()");
            }
        } else {//左树不为空的情况，先加上（，然后继续递归左树，再加）
            sb.append("(");
            tree2strChild(root.left, sb);
            sb.append(")");
        }
        //右树为空直接返回
        if (root.right == null) {
            return;
        } else {//跟左树同理
            sb.append("(");
            tree2strChild(root.right, sb);
            sb.append(")");
        }
    }

    public String tree2str(TreeNode root) {
        if (root == null) {
            return null;
        }
        StringBuilder sb = new StringBuilder();
        tree2strChild(root, sb);
        return toString();
    }

    public static String truncateSentence(String s, int k) {
        int length = s.length();
        int count = 0;
        int end = 0;
        for (int i = 1; i <= length; i++) {
            if (length == i || s.charAt(i) == ' ') {
                count++;
                if (count == k) {
                    end = i;
                    break;
                }
            }
        }
        return s.substring(0, end);
    }

    public static void main1(String[] args) {
        String s = "Hello how are you Contestant";
        System.out.println(truncateSentence(s, 4));
    }

    public static void main(String[] args) {
        int x = 0;
        for (int z = 0; z < 5; z++) {
            if (z>=2)
            {
                x++;
            }
        }
        System.out.println(x);
    }



    public int removeElement(int[] nums, int val){
        int left=0;
        int right=nums.length-1;
        while(left<right){
            if(nums[left]==val){
                nums[left]=nums[right];
            }else{
                left++;
            }
        }
        return left;
    }
public boolean isHappy(int n){
        Set<Integer> set=new HashSet<>();

        while(n!=1&&!set.contains(n)){
            set.add(n);
            n=getNext(n);
        }
        return n==1;
}
    public int getNext(int n){
        int sum=0;
        int num=0;
        while(n>0){
             num=n%10;
            n=n/10;
            sum+=num*num;
        }
        return sum;
    }

    public boolean isUgly(int n) {
        if(n<=0){
            return false;
        }
        int []m={2,3,5};
        for (int x:m){
            while(n%x==0){
                n=n/x;
            }
        }
        return n==1;
    }

    public boolean isPalindrome(int x){
        Stack<Integer> stack=new Stack<>();
        int i=0;
        int []nums=new int [100];
        while(x>0){
            stack.push(x%10);
            nums[i]=x%10;
            i++;
            x/=10;
        }
        int j=0;
        while(!stack.empty()){
            if(stack.peek()!=nums[j]){
                return false;
            }
            j++;
            stack.pop();

        }
        return true;
    }

    boolean isCompleteTree(TreeNode root){
        Queue<TreeNode>queue=new LinkedList<>();
        if(root==null){
            return true;
        }
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode cur=queue.poll();
            if(cur!=null){
                queue.offer(root.left);
                queue.offer(root.right);
            }
            else{
                break;
            }
        }
        while(!queue.isEmpty()){
           TreeNode top=queue.peek();
            if (top != null) {
                return false;
            }
            queue.poll();
        }
        return true;
    }
}
